package leetcode.easy.q108;

import leetcode.util.TreeNode;
import lombok.extern.slf4j.Slf4j;

import static leetcode.util.Utils.toArray;

@Slf4j
public class Q {
    public static void main(String[] args) {
//      log.info("res:{}",new Solution().sortedArrayToBST(toArray(-10,-3,0,5,9)));
      log.info("res:{}",new Solution().sortedArrayToBST(toArray(10,7,15,5,9,8)));
    }
}
@Slf4j
class Solution {
    private int BALANCE_SCALE = 1;

    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST1(nums);
    }

    /***
     从左往右构建，构建过程中不断调整，不会用到数组有序的性质
     */
    private TreeNode buildBST1(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        TreeNode node = new TreeNode(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            node = insert(nums[i], node);
        }
        return node;

    }

    /***
     插入一个节点，并返回节点
     */
    private TreeNode insert(int insertVal, TreeNode subTreeRoot) {
        //子树为空，找到插入点
        if (subTreeRoot == null) {
            return new TreeNode(insertVal);
        }
        if (insertVal > subTreeRoot.val) {
            subTreeRoot.right = insert(insertVal, subTreeRoot.right);
        } else if (insertVal < subTreeRoot.val) {
            subTreeRoot.left = insert(insertVal, subTreeRoot.left);
        }else {
            //a same node, do nothing
        }
        return balance(subTreeRoot);

    }

    private TreeNode balance(TreeNode subTreeRoot) {
        if (subTreeRoot == null) {
            return subTreeRoot;
        }
        //得到高度
        int leftHeight = getHeight(subTreeRoot.left);
        int rightHeight = getHeight(subTreeRoot.right);
        if (leftHeight - rightHeight > BALANCE_SCALE) {
            int llHeight = getHeight(subTreeRoot.left.left);
            int lrHeight = getHeight(subTreeRoot.left.right);
            //左儿子左子树插入
            if (llHeight > lrHeight) {
                subTreeRoot = ll(subTreeRoot);
            } else if (lrHeight > llHeight) {//左儿子右子树插入
                subTreeRoot = lr(subTreeRoot);
            } else {
                log.info("possible1.");
                //possible?
            }
        } else if (rightHeight - leftHeight > BALANCE_SCALE) {
            int rrHeight = getHeight(subTreeRoot.right.right);
            int rlHeight = getHeight(subTreeRoot.right.left);
            //右儿子右子树插入
            if (rrHeight > rlHeight) {
                subTreeRoot = rr(subTreeRoot);
            } else if (rlHeight > rrHeight) {
                subTreeRoot = rl(subTreeRoot);
            } else {
                log.info("possible2.");
                //possible?
            }
        }
        return subTreeRoot;
    }

    private TreeNode ll(TreeNode root) {
        TreeNode newRoot = root.left;
        root.left = newRoot.right;
        newRoot.right = root;
        return newRoot;
    }

    private TreeNode lr(TreeNode root) {
        root.left = rr(root.left);
        return ll(root);
    }

    private TreeNode rl(TreeNode root) {
        root.right = ll(root.right);
        return rr(root);
    }

    private TreeNode rr(TreeNode root) {
        TreeNode newRoot = root.right;
        root.right = newRoot.left;
        newRoot.left = root;
        return newRoot;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return -1;
        } else {
            return Math.max(getHeight(node.left) + 1, getHeight(node.right) + 1);
        }
    }
}